#define _CRT_SECURE_NO_WARNINGS
//#include "Heap.h"
//int main()
//{
//	Heap hp;
//	HeapInit(&hp);
//	HeapPush(&hp, 1);
//	HeapPush(&hp, 2);
//	HeapPush(&hp, 3);
//	HeapPush(&hp, 4);
//	HeapPush(&hp, 5);
//	while (!HeapEmpty(&hp))
//	{
//		printf("%d ", HeapTop(&hp));
//		HeapPop(&hp);
//	}
//	HeapDestroy(&hp);
//	return 0;
//}

#include "Heap.h"
//void Swap(int* p1, int* p2)
//{
//	int tmp = *p1;
//	*p1 = *p2;
//	*p2 = tmp;
//}
//
//void AdjustDown(int* arr, int parent, int size)
//{
//	int child = 2 * parent + 1;
//	while (child < size)
//	{
//		if (child + 1 < size && arr[child + 1] > arr[child])
//		{
//			child++;
//		}
//		if (arr[parent] < arr[child])
//		{
//			Swap(&arr[parent], &arr[child]);
//		}
//		parent = child;
//		child = 2 * parent + 1;
//	}
//}
#include <time.h>
void HeapSort(int* arr, int size)
{
	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, size);
	}
	int end = size;
	for (int i = 0; i < end ; i++)
	{
		Swap(&arr[0], &arr[size - 1]);
		size--;
		AdjustDown(arr, 0, size);
	}
}
void test1()
{
	int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
	HeapSort(arr,sizeof(arr)/sizeof(int));
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
	{
		printf("%d ", arr[i]);
	}
}


void test_topk()
{
	int arr[20];
	for (int i = 0; i < 20; i++)
	{
		arr[i] = rand() % 100;
		printf("%d ", arr[i]);
	}
	int size = 4;
	int heap[4];
	for (int i = 0; i < 4; i++)
	{
		heap[i] = arr[i];
	}
	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(heap, i, 4);
	}
	for (int i = 5; i < 20; i++)
	{
		if (arr[i] > heap[0])
		{
			heap[0] = arr[i];
			AdjustDown(heap, 0,4);
		}
	}
	printf("\n");
	for (int i = 0; i < 4; i++)
	{
		printf("%d ", heap[i]);
	}

}
int main()
{
	srand((unsigned int)time(NULL));
	//test1();
	test_topk();
	return 0;
}